#include <iostream>


using namespace std;
const int N = 2e5 + 5;

struct tr {
    int l, r, n;
} t[N * 32];

int x = 1, head[N], num;
void build(int from, int l, int r) {
    t[x] = t[from]; ++t[x++].n;
    if (l == r) return ;
    int mid = l + r >> 1;
    if (num <= mid) t[x - 1].l = x, build(t[from].l, l, mid);
    else t[x - 1].r = x, build(t[from].r, mid + 1, r);
}
int check(int l, int r, int L, int R, int k) {
    if (L == R) return L;
    int mid = L + R >> 1, g = 0;
    if (t[t[r].r].n - t[t[l].r].n && mid < k) g = check(t[l].r, t[r].r, mid + 1, R, k);
    if (!g && t[t[r].l].n - t[t[l].l].n) g = check(t[l].l, t[r].l, L, mid, k);
    return g;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> num, head[i] = x, build(head[i - 1], 0, 1e9);
    for (int i = 1; i <= m; ++ i) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        int aJ = check(head[l2 - 1], head[r2], 0, 1e9, 1e9), aI;  // get[l2, r2]区间最大aj, 并*2+1得到理论上最佳对手ai
        while (true) {
            aI = check(head[l1 - 1], head[r1], 0, 1e9, aJ << 1 | 1); // get[l1, r2]区间<=ai的最大值
            if (!aI) { cout << 0 << '\n'; break; }
            if (aI > aJ) { cout << aI + aJ << '\n'; break; }
            aJ = check(head[l2 - 1], head[r2], 0, 1e9, aI - 1);
            if (!aJ) { cout << 0 << '\n'; break; }
            if (aJ >= aI / 2) { cout << aI + aJ << '\n'; break; }
        }
    }
    return 0;
}